// @algorithm @lc id=673 lang=cpp 
// @title number-of-longest-increasing-subsequence


// @test([1,3,5,4,7])=2
// @test([2,2,2,2,2])=5
// @test([1,1,1,2,2,2,3,3,3])=27
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> dp(n, 1), cnt(n, 1);
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(nums[i] <= nums[j])
                    continue;
                if(dp[i] == dp[j]+1)
                    cnt[i] += cnt[j];
                else if(dp[i] < dp[j]+1){
                    cnt[i] = cnt[j];
                    dp[i] = dp[j] + 1;
                }
            }

            if(maxLen == dp[i])
                ans += cnt[i];
            else if(maxLen < dp[i]){
                ans = cnt[i];
                maxLen = dp[i];
            }
        }
        return ans;
    }
};